Optical computing is viewed as a promising computational model. The classic deterministic Turing Machine model is the base for the computation complexity classes, since any (electronic) computer can be viewed as a version of a Turing Machine. The definition of the classical Turing Machine has been extended to the case of a non-deterministic Turing Machine [M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. Freeman Company, 1990], where the choice of the next state is chosen arbitrarily; in fact, all possible choices should be examined in order to reject the input. The definition of non-deterministic Turing Machine classifies many very important classic problems, such as the traveling salesman problem, as problems that can be solved in polynomial time by the non-deterministic Turing Machine.
A model for implementing a deterministic Turing Machine based on optical ray tracing is presented in [J. H. Reif, D. Tygar, and A. Yoshida, “Computability and Complexity of Ray Tracing”, Discrete and Computational Geometry 11 (1994), pp. 265–297]. It would be very desirable to extend this model to the case of non-determinism and even more desirable to provide a device capable of carrying out this model.
It is an object of the present invention to provide a model of an optical computation device that can implement non-deterministic Turing Machines up to a bounded input length.
Further purposes and advantages of this invention will appear as the description proceeds.